package leetcode_800;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 *@author 周杨
 *RabbitsInForest_781 森林里有很多兔子  他们分成组说除了它们组 其他的有多少和自己颜色一样的 问最少有多少兔子
 *describe:贪心思想 给喊同一数字的兔子分组 如果超过了最大数量 那么换一种颜色重新分组 AC 52%
 *2018年10月21日 上午11:07:28
 */
public class RabbitsInForest_781 {
	public int numRabbits(int[] answers) {
		int res = 0;
		int len = answers.length;
		if (len == 0)
			return 0;
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		for (int answer : answers) {
			map.put(answer, map.getOrDefault(answer, 0) + 1);
		}
		for (Integer key : map.keySet()) {//有多少人叫key 
			int group = map.get(key) / (key+1);//可以分成多少组
			if (map.get(key) % (key + 1) == 0) {//整除了 那么就是这么多颜色
				res += map.get(key);
			} else {//否则 再加上这么多组 和 另外的颜色
				res += (group + 1) * (key + 1);
			}
		}
		return res;
    }
}
